package string;

import com.sun.applet2.preloader.event.InitEvent;

import java.util.*;

/**
 * 227. Basic Calculator II
 Medium

 Implement a basic calculator to evaluate a simple expression string.

 The expression string contains only non-negative integers, +, -, *, / operators and empty spaces .
 The integer division should truncate toward zero.

 Example 1:

 Input: "3+2*2"
 Output: 7

 Example 2:

 Input: " 3/2 "
 output: 1

 example 3:

 Input: " 3+5 / 2 "
 Output: 5
 Note:

 You may assume that the given expression is always valid.
 Do not use the eval built-in library function.
 */
public class Q227_BasicCalculatorII {
    /**
     * A digital stack, a symbolic stack
     * + - decreasing priority
     * * / processing firstly
     * " " continue
     * <p>
     * assuming input example:
     * "42"
     * "2+ 4 2"
     * "2 + 4 * 2 / 3"
     *
     * 中缀转换成后缀
     *  符号判断 cur==‘+’ pre放入
     *   cur=='*' pre=='*'放入
     */
    private int calculate(String s) {
        Stack<String> symStack = new Stack<>();
        List<String> backExp = new ArrayList<>();
        char[] chs = s.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == '-' || chs[i] == '+') {
                while (!symStack.isEmpty()) {
                    backExp.add(symStack.pop()); // 弹出优先级相同或以上的栈内运算符
                }
                symStack.add(String.valueOf(chs[i]));
            } else if (chs[i] == '*' || chs[i] == '/') {
                while (!symStack.isEmpty() && (symStack.lastElement().equals("*") || symStack.lastElement().equals("/"))) {
                    backExp.add(symStack.pop()); // 弹出优先级相同或以上的栈内运算符
                }
                symStack.add(String.valueOf(chs[i]));
            } else if (chs[i] != ' '){
                StringBuilder sb = new StringBuilder();
                while (i<s.length() && chs[i]!=' ' && chs[i]>='0' && chs[i]<='9') {
                    sb.append(chs[i]-'0');
                    i++;
                }
                backExp.add(sb.toString());
                i--;
            }
        }
        while (!symStack.isEmpty()) {
            backExp.add(symStack.pop());
        }
        //23* 4+
        Stack<Integer> calStk = new Stack<Integer>();
        for (String c : backExp) {
            System.out.println(c);
            // 1.数字，入栈
            if (!"+".equals(c) && !"-".equals(c) && !"/".equals(c) && !"*".equals(c)) {
                calStk.push(Integer.valueOf(c)); // string to int
            }
            // 2.非数字，则为符号，出栈两个元素计算出结果然后再入栈该计算值
            else {
                int n2 = calStk.pop();
                int n1 = calStk.pop();
                int ans = operate(n1, n2, c.charAt(0));
                System.out.println(n1+""+c.charAt(0)+""+n2+"="+ans);
                calStk.add(ans);
            }
        }
        return calStk.pop();
    }

    private int operate(int n1, int n2, Character ch) {
        if (ch == '+') {
            return n1 + n2;
        } else if (ch == '-') {
            return n1 - n2;
        } else if (ch == '*') {
            return n1 * n2;
        } else {
            return n1 / n2;
        }
    }

    /**
     * calculator optimization
     */
    private int calculateOpt(String s) {
        char[] chs = s.toCharArray();
        Stack<Integer> digStack = new Stack<>();
        char lastOp = '+';
        for (int i=0; i<chs.length; i++) {
            if (chs[i] == ' ') {
                continue;
            }
            if (chs[i]>='0' && chs[i]<='9') {
                int num = 0;
                while (i<s.length() && chs[i]>='0' && chs[i]<='9') {
                    num = num * 10 + chs[i] - '0';
                    i++;
                }
                i--;
                if (lastOp == '+') {
                    digStack.add(num);
                } else if (lastOp == '-') {
                    digStack.add(-num);
                } else {
                    digStack.add(operate(digStack.pop(), num, lastOp));
                }
            } else {
                lastOp = chs[i];
            }
        }
        return calculateAns(digStack);
    }

    private int calculateAns(Stack<Integer> digStack) {
        int ans = 0;
        while (!digStack.isEmpty()) {
            ans += digStack.pop();
        }
        return ans;
    }

    public static void main(String[] args) {
        Q227_BasicCalculatorII q227_basicCalculatorII = new Q227_BasicCalculatorII();
        int res = q227_basicCalculatorII.calculate("2+3*4");
        System.out.println(res);
        int res1 = q227_basicCalculatorII.calculateOpt("2+3*4");
        System.out.println(res1);
    }

}